package com.zang.tree;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

/**
 * @author ZVerify
 * @since 2022/11/02 12:40
 * @see <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/submissions/">...</a>
 **/
public class 二叉树的最近公共祖先 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        TreeNode treeNode =  dfs(root,p,q);
        if (treeNode==null) return root;
        else return treeNode;
    }

    private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {

        if (root==null){
            return null;
        }
        TreeNode left = dfs(root.left, p, q);
        TreeNode right = dfs(root.right, p, q);
        // 当前节点为p或者q直接返回
        if (root==q || root==p) {
            return root;
        }
        // 左右都不为null直接返回
        if (left!=null && right!=null) return root;
        // 在右边找到返回右边的
        if (left==null && right!=null) return right;
        // 在左边找到返回左边的
        if (right==null && left!=null ) return left;
        // 所有都不符合返回null
        return null;
    }
}
